
//42.接雨水
class Solution {
public:
    int trap(vector<int>& nums) {
        //使用前缀和,从左到右和从右到左
        //从左到右:假设右边的柱子无限高,看当前这个位置雨水的高度
        //从右向左:假设左边的柱子无限高,看当前这个位置雨水的高度

        int n=nums.size();
        vector<int> left(n);
        //此处可以不使用单调栈,直接记录已经遍历部分柱子的最大值即可
        int len=0;
        for(int i=0;i<n;i++)
        {
            len=max(len,nums[i]);
            left[i]=len;
        }
        len=0;
        vector<int> right(n);
        for(int i=n-1;i>=0;i--)
        {
            len=max(len,nums[i]);
            right[i]=len;
        }

        //因为柱子不一定是无限高,所以不一定满足条件,
        //但是此时right和left数组中已经存储了从左向右和从右向左可以达到的高度,取两者的较小值就是水面的高度
        int ret=0;
        for(int i=0;i<n;i++)
        {
            ret+=min(right[i],left[i])-nums[i];
        }
        return ret;
    }
};